package problem.year2022.February;

import java.util.*;

/**
 * @author Liu.Liangyuan 15439
 * @version $Id: Day0215.java, v 0.1 2022年02月15日 1:25 下午 Liangmu Exp $$
 */
public class Day0215 {

    public static void main(String[] args) {
        int[][] matrix ={{3,6},{7,1},{5,2},{4,8}};
        List<Integer> integers = luckyNumbers(matrix);
        System.out.println(Arrays.toString(integers.toArray()));
    }

    /**
     * 给你一个 m * n 的矩阵，矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。
     * <p>
     * 幸运数是指矩阵中满足同时下列两个条件的元素：
     * <p>
     * 在同一行的所有元素中最小
     * 在同一列的所有元素中最大
     * <p>
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/lucky-numbers-in-a-matrix
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param matrix
     * @return
     */
    public static List<Integer> luckyNumbers(int[][] matrix) {
        Set<Integer> set = new HashSet<>();
        int rowLen = matrix.length;
        int colLen = matrix[0].length;
        // row min
        for (int i = 0; i < rowLen; ++i) {
            int min = matrix[i][0];
            int temp = i * colLen;
            int index = temp;
            for (int j = 1; j < colLen; ++j) {
                if (min > matrix[i][j]) {
                    min = matrix[i][j];
                    index = temp + j;
                }
            }
            set.add(index);
        }
        List<Integer> res = new ArrayList<>(1);
        // col min
        for (int i = 0; i < colLen; ++i) {
            int max = matrix[0][i];
            int index = i;
            for (int j = 1; j < rowLen; ++j) {
                if (max < matrix[j][i]) {
                    max = matrix[j][i];
                    index = i + j * colLen;
                }
            }
            if (set.contains(index)) {
                res.add(matrix[index / colLen][index % colLen]);
            }
        }
        return res;
    }
}
